package com.lfg.leetcode.leetcode0;


public class No34SearchRange {


    public static int[] searchRange(int[] nums, int target) {
        int[] ret = new int[]{-1, -1};
        if (nums.length == 0) {
            return ret;
        }

        int left = -1;
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int middle = (i + j) / 2;
            if (target == nums[i]) {
                left = i;
                break;
            } else if (target == nums[middle]) {
                j = middle;
                i++;
            } else if (target < nums[middle]) {
                j = middle - 1;
                i++;
            } else if (target > nums[middle]) {
                i = middle + 1;
            }

        }
        if (left == -1) {
            return ret;
        }
        int right = -1;
        i = 0;
        j = nums.length - 1;
        while (i <= j) {
            int middle = (i + j) / 2;
            if (target == nums[j]) {
                right = j;
                break;
            } else if (target == nums[middle]) {
                i = middle;
                j--;
            } else if (target < nums[middle]) {
                j = middle - 1;
            } else if (target > nums[middle]) {
                i = middle + 1;
                j--;
            }
        }
        ret[0] = left;
        ret[1] = right;
        return ret;
    }


    public static void main(String[] args) {
//        int ret = search(new int[]{9,10,11,0,1,2, 3,4,5,6,7,8},1);
        int[] ret = searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8);
        for (int i : ret) {
            System.out.println(i);
        }
    }
}

